class Solution {
public:
  int findTargetSumWays(vector<int>& nums, int S) {

    int n = nums.size();
    // dp[i][j]表示用nums[0..i]表示j的方法个数
    // 因为所有nums相加可能是负数，所以要多开S个空间

    int maxSum = accumulate(nums.begin(), nums.end(), 0);
    if(abs(S) > abs(maxSum)){
      return 0;
    }

    int dp[n + 1][2 * maxSum + 1];
    memset(dp, 0, sizeof(dp));

    // 因为下标不能为负数，所以要加上maxSum变为非负数
    dp[0][-nums.at(0) + maxSum] += 1;
    dp[0][nums.at(0) + maxSum] += 1;

    // dp[i][j + maxSum] = dp[i - 1][j + maxSum - nums.at(i)] + dp[i - 1][j + maxSum + nums.at(i)]
    for(int i = 1; i < n; ++i){
      for(int j = -maxSum; j <= maxSum; ++j){
        if((j + maxSum + nums.at(i)) >= 2 * maxSum + 1){
          // 再加数就大于S了，所以只加dp[i - 1][j + maxSum - nums.at(i)]
          dp[i][j + maxSum] = dp[i - 1][j + maxSum - nums.at(i)] + 0;
        }else if((j + maxSum - nums.at(i)) < 0){
          // 再减就小于-S了，所以只加dp[i - 1][j + maxSum + nums.at(i)]
          dp[i][j + maxSum] = dp[i - 1][j + maxSum + nums.at(i)] + 0;
        }else{
          dp[i][j + maxSum] = dp[i - 1][j + maxSum - nums.at(i)] + dp[i - 1][j + maxSum + nums.at(i)];
        }
      }
    }

    return dp[n - 1][S + maxSum];

  }
};